package gambit.jogador;

import gambit.core.Tabuleiro;

import java.util.ArrayList;


public class Minimax {

	private int profundidade;
	
	private ArrayList<Node>[] listaNohsPorNivel;
	
	public Minimax(int profundidade){
		
		// Cria��o do array de listas de n�s
		// �ndice do array = profundidade da lista
		
		this.profundidade = profundidade;
		this.listaNohsPorNivel = new ArrayList[profundidade+1];	
		for(int i = 0; i < profundidade+1; i++){
			listaNohsPorNivel[i] = new ArrayList<Node>();
		}
	}
	
	public void arvore(Tabuleiro tab, int n){
		arvore(tab, n, null);
	}

	public void arvore(Tabuleiro tab, Integer n, Node pai) {

		if(n >= 0){
			Node nodetemp = new Node(profundidade - n);
			nodetemp.setTab(tab);
			nodetemp.setPai(pai);
			listaNohsPorNivel[profundidade - n].add(nodetemp);
			
			if(pai != null) 
				pai.getFilhos().add(nodetemp);
			
			if((profundidade - n) % 2 == 1)
				tab = Tabuleiro.inverter(tab);
			
			ArrayList<Tabuleiro> tablist = tab.listarPossiveisJogadas();
			for (int i = 0; i < tablist.size(); i++) {
				if((profundidade - n) % 2 == 1)
					tablist.set(i, Tabuleiro.inverter(tablist.get(i)));
				
				arvore(tablist.get(i), n - 1, nodetemp);
			}
		}
	}

	public void atribuirMinMax(Node noh) {

		if (noh.getFilhos().size() == 0) {
			noh.setMinimax(Utilidade.getCusto(noh.getTab()));
		} else {
			if (noh.getDepth() % 2 == 0) {
				int max = -Integer.MAX_VALUE;
				for (Node d : noh.getFilhos()) {
					if (d.getMinimax() ==-Integer.MAX_VALUE) {
						atribuirMinMax(d);
					}
					if (d.getMinimax() > max)
						max = d.getMinimax();
				}
				noh.setMinimax(max);
			} else {
				int min = Integer.MAX_VALUE;
				for (Node d : noh.getFilhos()) {
					if (d.getMinimax() ==Integer.MAX_VALUE) {
						atribuirMinMax(d);
					}
					if (d.getMinimax() < min)
						min = d.getMinimax();
				}
				noh.setMinimax(min);
			}
		}

	}

	public Integer mtdf(Tabuleiro root, Integer f, Integer d) {
		int g = f;
		int upperbound = +66666;
		int lowerbound = -66666;
		int beta;

		// repeat
		do {
			if (g == lowerbound) {
				beta = g + 1;
			} else
				beta = g;

			// g = alphaBetaWithMemory(root, beta - 1, beta, d);
			if (g < beta) {
				upperbound = g;
			} else
				lowerbound = g;
		} while (lowerbound < upperbound);
		return g;
	}
	
	public Tabuleiro melhorJogada() {
		atribuirMinMax(listaNohsPorNivel[0].get(0)); //pega tabuleiro atual
		int valor = listaNohsPorNivel[0].get(0).getMinimax();
		int i;
		Tabuleiro tabuleiro = new Tabuleiro();
		
		for (i=0; i<listaNohsPorNivel[1].size(); i++) {
			if (listaNohsPorNivel[1].get(i).getMinimax()==valor) {
				tabuleiro = listaNohsPorNivel[1].get(i).getTab();
				i = listaNohsPorNivel[1].size();
			}
		}
		
		return tabuleiro;
		
	}

	// public Integer alphaBetaWithMemory(Tabuleiro n, Integer alpha , Integer
	// beta , Integer d) {
	// if retrieve(n) == OK then /* Transposition table lookup */
	//		 
	// if n.lowerbound >= beta then return n.lowerbound;
	// if n.upperbound <= alpha then return n.upperbound;
	// alpha := max(alpha, n.lowerbound);
	// beta := min(beta, n.upperbound);
	//		 
	// if d == 0 then g := evaluate(n); /* leaf node */
	// else if n == MAXNODE then
	//		 
	// g := -INFINITY; a := alpha; /* save original alpha value */
	// c := firstchild(n);
	// while (g < beta) and (c != NOCHILD) do
	//		 
	// g := max(g, AlphaBetaWithMemory(c, a, beta, d - 1));
	// a := max(a, g);
	// c := nextbrother(c);
	//		 
	// else /* n is a MINNODE */
	//		 
	// g := +INFINITY; b := beta; /* save original beta value */
	// c := firstchild(n);
	// while (g > alpha) and (c != NOCHILD) do
	//		 
	// g := min(g, AlphaBetaWithMemory(c, alpha, b, d - 1));
	// b := min(b, g);
	// c := nextbrother(c);
	//		 
	// /* Traditional transposition table storing of bounds */
	// /* Fail low result implies an upper bound */
	// if g <= alpha then n.upperbound := g; store n.upperbound;
	// /* Found an accurate minimax value - will not occur if called with zero
	// window */
	// if g > alpha and g < beta then
	//		 
	// n.lowerbound := g; n.upperbound := g; store n.lowerbound, n.upperbound;
	// /* Fail high result implies a lower bound */
	// if g >= beta then n.lowerbound := g; store n.lowerbound;
	// return g;
	//	
	// }

}
